#include <iostream>
using namespace std;
#include <vector>
#include <unordered_map>

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        int ret = 0;
        int sum = 0;
        hash[0] = 1;
        for (auto s : nums)
        {
            sum += s;
            int n = (sum % k + k) % k;
            if (hash.count(n))
            {
                ret += hash[n];
            }
            hash[n]++;
        }
        return ret;
    }
};

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> hash;
        int n = nums.size();
        hash[0] = -1;
        int sum = 0;
        int ret = 0;
        for (int i = 0; i < n; i++)
        {
            sum += (nums[i] == 0 ? -1 : 1);
            if (hash.count(sum))
            {
                ret = max(ret, i - hash[sum]);
            }
            else
            {
                hash[sum] = i;
            }
        }
        return ret;
    }
};

class Solution {
public:
    int tribonacci(int n) {
        int sum = 0;
        if (n == 0)
        {
            return 0;
        }
        else if (n == 1 || n == 2)
        {
            return 1;
        }
        else
        {
            int t0 = 0;
            int t1 = 1;
            int t2 = 1;
            for (int i = 3; i <= n; i++)
            {
                sum = t0 + t1 + t2;
                t0 = t1;
                t1 = t2;
                t2 = sum;
            }
        }
        return sum;
    }
};

class Solution {
public:
    int waysToStep(int n) {
        long long sum = 0;
        if (n == 0)
        {
            return 0;
        }
        if (n == 1)
        {
            return 1;
        }
        else if (n == 2)
        {
            return 2;
        }
        else if (n == 3)
        {
            return 4;
        }
        else
        {
            long long t1 = 1;
            long long t2 = 2;
            long long t3 = 4;
            for (int i = 4; i <= n; i++)
            {
                sum = t1 % 1000000007 + t2 % 1000000007 + t3 % 1000000007;
                t1 = t2;
                t2 = t3;
                t3 = sum;
            }
        }
        return sum % 1000000007;
    }
};

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> ret(n + 1);
        for (int i = 2; i < n + 1; i++)
        {
            ret[i] = min(ret[i - 1] + cost[i - 1], ret[i - 2] + cost[i - 2]);
        }
        return ret[n];
    }
};

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> ret(n);
        ret[n - 1] = cost[n - 1];
        ret[n - 2] = cost[n - 2];
        for (int i = n - 3; i >= 0; i--)
        {
            ret[i] = min(ret[i + 1], ret[i + 2]) + cost[i];
        }
        return min(ret[0], ret[1]);
    }
};

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        int p1 = 0;
        int p2 = 0;
        int p3 = 0;
        p1 = s[0] == '0' ? 0 : 1;
        if (n == 1)
        {
            return p1;
        }
        if (p1 != 0 && s[1] != '0')
        {
            p2++;
        }
        int t = (s[0] - '0') * 10 + (s[1] - '0');
        if (t > 9 && t < 27)
        {
            p2++;
        }
        for (int i = 2; i < n; i++)
        {
            if (s[i] != '0')
            {
                p3 += p2;
            }
            int t = (s[i - 1] - '0') * 10 + (s[i] - '0');
            if (t > 9 && t < 27)
            {
                p3 += p1;
            }
            p1 = p2;
            p2 = p3;
            p3 = 0;
        }
        return p2;
    }
};

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> ret(n + 1);
        ret[0] = 1;
        ret[1] = s[0] != '0';
        for (int i = 2; i <= n; i++)
        {
            if (s[i - 1] != '0')
            {
                ret[i] += ret[i - 1];
            }
            int t = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
            if (t > 9 && t < 27)
            {
                ret[i] += ret[i - 2];
            }
        }
        return ret[n];
    }
};